package com.sise.Backtracking;

import java.util.LinkedList;
import java.util.List;

/**
 *      回溯算法（Backtracking） - 本质有点像 DFS，深度优先遍历
 *      解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
 *          1、路径：也就是已经做出的选择。
 *          2、选择列表：也就是你当前可以做的选择。
 *          3、结束条件：也就是到达决策树底层，无法再做选择的条件。
 *
 *
 *      通用模板：其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
 *
 *      result = []
 *      def backtrack(路径, 选择列表):
 *          if 满足结束条件:
 *              result.add(路径)
 *              return
 *
 *          for 选择 in 选择列表:
 *              做选择
 *              backtrack(路径, 选择列表)
 *              撤销选择
 */
public class Backtracking {

    /**
     *      46. 全排列
     *      给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     *      输入: [1,2,3]
     *      输出:
     *      [
     *          [1,2,3],
     *          [1,3,2],
     *          [2,1,3],
     *          [2,3,1],
     *          [3,1,2],
     *          [3,2,1]
     *      ]
     */

    // 创建结果集存储全部的可能性
    List<List<Integer>> res = new LinkedList<>();

    // 主函数
    public List<List<Integer>> permute(int[] nums) {
        // 记录 '路径'
        LinkedList<Integer> track = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        backTrack(nums, track, used);
        return res;
    }

    // 路径：记录在 track 中
    // 路径选择：nums 中不存在于 track 的那些元素
    // 结束条件：nums 中的元素全部在 track 中出现
    public void backTrack(int[] nums, LinkedList<Integer> track, boolean[] used){
        // 触发结束条件：当 track 收集全部数字后，便放入 res 中，return 返回上一层
        if (track.size() == nums.length){
            res.add(new LinkedList<>(track));
            return;
        }

        // 遍历 nums
        for (int i = 0; i < nums.length; i++){
            // 只有不在 track 中的元素才可以添加（排除不合法的选择） true 代表已被使用
            if (used[i] != true){
                // 做选择，将 数字加入到 track 中
                track.add(nums[i]);
                used[i] = true;
                // 进入下一层决策树中
                backTrack(nums, track, used);
                // 撤销选择，返回上一层
                track.removeLast();
                used[i] = false;
            }
        }
    }
}
